package HOT100;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 是阿秋啊
 * 括号生成
 * @date 2022/11/24 14:51
 **/
public class Num22 {
    List<String> ret = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder sb = new StringBuilder();
        fun(sb,0,0,n);
        return ret;
    }

    private void fun(StringBuilder sb, int left, int right, int n) {
        if (sb.length() >= 2 * n){
            ret.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append("(");
            fun(sb,left+1,right,n);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right < left) {
            sb.append(")");
            fun(sb,left,right+1,n);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}